<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        // 1. 优化的思路：把交换变成 “值的覆盖” 当后一个值小于前一个值时，不是每次都进行交换
        function insertSort(nums) {
            // 有用来存储最后一个停留的指针
            let last
            for (let i = 1; i < nums.length; i++) {
                // 把当前元素记忆
                let insertValue = nums[i]
                // j是上一个元素 当前元素和上一个元素进行比较
                for (let j = i - 1; j >= 0; j--) {
                    // 如果当前元素更小 就进行“赋值”操作
                    if (insertValue < nums[j]) {
                        // 如果交换了，那么last就是j的值
                        // 难点！如果后一个值小于前一个值 j是前一个值的索引 就让last等于j
                        last = j
                        nums[j + 1] = nums[j]
                    } else {
                        // “当前元素”比上一个元素大 就退出for循环比较
                        // 如果没有发生交换 那么last指针就指向的是j + 1说明j + 1的值大于j的值
                        // 如果后一个值更大 j + 1就是后一个值 让last等于j + 1
                        last = j + 1
                        break
                    }
                }
                nums[last] = insertValue
            }
            return nums
        }
        // console.log(insertSort([5, 2, 3, 1]));
        console.log(insertSort([-4, 0, 7, 4, 9, -5, -1, 0, -7, -1])); // 这个测试用例无法通过

        // console.time('init1')
        // let initArr = [3, 5, 1, 9, 4, 2, 11, 8]
        // console.log(insertSort(initArr));
        // console.timeEnd('init1')

        // 采用赋值的形式 比直接交换 速度快了3倍
        // let initArr = []
        // for (let i = 10000; i > 0; i--) {
        //     initArr.push(i)
        // }
        // console.time('init1')
        // console.log(insertSort(initArr));
        // console.timeEnd('init1')

    </script>
</body>

</html>